package 动态规划;

import java.util.Arrays;

public class No188买卖股票的最佳时机IV {

    /**
     * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 示例 1：
     * 输入：k = 2, prices = [2,4,1]
     * 输出：2
     * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
     * 示例 2：
     * 输入：k = 2, prices = [3,2,6,5,0,3]
     * 输出：7
     * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     *      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
     *  
     * 提示：
     * 0 <= k <= 100
     * 0 <= prices.length <= 1000
     * 0 <= prices[i] <= 1000
     */

    public int maxProfit(int k, int[] prices) {

        if(prices.length<1||k==0){
            return 0;
        }

        k+=1;//注意,包括第k次交易
        //K次交易 6种状态
        int[][][] dp=new int[prices.length][k+1][2];//k天的k次交易的6种状态

        dp[0][0][0]= 0;
        dp[0][0][1]= Integer.MIN_VALUE;
        dp[0][1][0]= 0;
        dp[0][1][1]= -prices[0];
        for (int i = 0; i < prices.length; i++) {
            //默认每天的第2~k次交易都为负无穷
            for (int j = 2; j < k; j++) {
                dp[i][j][1]=Integer.MIN_VALUE;
            }
        }

        for (int i = 1; i < prices.length; i++) {
            dp[i][0][0]=dp[i-1][0][0];
            dp[i][0][1]=dp[i-1][0][1];
            for (int j = 1; j < k; j++) {
//                System.out.println("不动:"+dp[i-1][j][0]+",之前持有时手里的钱:"+dp[i-1][j][1]+",今天的股价:"+prices[i]);
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);//今天卖出昨天持有的
//                System.out.println(dp[i][j][0]);
//                System.out.println("不动:"+dp[i-1][j][1]+",之前不持有时手里的钱:"+dp[i-1][j-1][0]+",今天的股价:"+prices[i]);
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);//今天买入
//                System.out.println(dp[i][j][1]);
            }
//            System.out.println("---");
        }

        int result=0;

        for (int i = 0; i < k; i++) {
            result=Math.max(result,dp[prices.length-1][i][0]);
        }

        return result;
    }

    //二维模式
    public int maxProfit2(int k, int[] prices) {

        if(prices.length<1||k==0){
            return 0;
        }

        k+=1;//注意,包括第k次交易
        //K次交易 6种状态
        int[][] dp=new int[k+1][2];//k天的k次交易的6种状态

        dp[0][0]= 0;
        dp[0][1]= Integer.MIN_VALUE;
        dp[1][0]= 0;
        dp[1][1]= -prices[0];
        for (int j = 2; j < k; j++) {
            dp[j][1]=Integer.MIN_VALUE;
        }

        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j < k; j++) {
                dp[j][0]=Math.max(dp[j][0],dp[j][1]+prices[i]);
                dp[j][1]=Math.max(dp[j][1],dp[j-1][0]-prices[i]);
            }
        }

        int result=0;

        for (int i = 0; i < k; i++) {
            result=Math.max(result,dp[i][0]);
        }

        return result;
    }

    public static void main(String[] args) {
        No188买卖股票的最佳时机IV n=new No188买卖股票的最佳时机IV();
        int result = n.maxProfit(6, new int[]{2,4});
        System.out.println(result);
    }

}
